# -*- coding: UTF-8 -*-
numbers = [7, 8, 3, 6, 0, 2, 1, 4, 5, 9]
print("元数据：",numbers)

def max_heapify(nums,lo,hi):
    dad = lo         # 父节点的位置
    son = 2 * dad + 1   # 子节点的位置
    tmp = nums[lo]   # 最原来的根的值
    while son <= hi: #若子节点指标在范围内才做比较
        if son + 1 <= hi and nums[son+1] > nums[son]: # 如果右孩子存在并且右孩子更大
            son += 1
        if tmp < nums[son]: # 如果最原来的根的值比孩子小
            nums[dad] = nums[son]  # 把孩子向上移动一层
            dad = son
            son = 2 * dad + 1
        else:
            break
    nums[dad] = tmp# 最原来的根的值放到对应的位置上(叶子节点)

def heap_sort(nums):
    length = len(nums) # 数组长度
    # 构建堆
    for i in range(length//2-1,-1,-1):
        max_heapify(nums,i,length-1)
    
    #  排序
    for l in range(length-1, -1, -1):    # l表示堆最后一个元素的位置
        nums[0], nums[l] = nums[l], nums[0]
        # 堆的大小少了一个元素 （l-1）
        max_heapify(nums, 0, l-1)

 

heap_sort(numbers)
print( "排序后：",numbers )


